/**
 * 
 */
package leetCode;

import java.util.HashMap;

/**
 * @author zhong
 *
 */
public class ClosestLeafinaBinaryTree {
	public static class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	int minDis = Integer.MAX_VALUE;
	int res;

	HashMap<Integer, Integer> dis2Leaf = new HashMap<>();// 当前节点的最近叶距离及对应值
	HashMap<Integer, Integer> dist2Tar = new HashMap<>();// 当前节点到target的值

	/**
	 * 
	 * @param root
	 * @param k
	 * @return 计算出最近的叶节点的值
	 */
	public int findClosestLeaf(TreeNode root, int k) {
		int le = Integer.MAX_VALUE, ri = Integer.MAX_VALUE;
		int disLeaf = -1;
		if (root.left == null && root.right == null) {
			dis2Leaf.put(root.val, 0);
		} else {
			if (root.left != null) {
				le = findClosestLeaf(root.left, k);
				disLeaf = dis2Leaf.get(root.left.val);
			}
			if (root.right != null) {
				ri = findClosestLeaf(root.right, k);
				disLeaf = Math.min(dis2Leaf.get(root.right.val), disLeaf);
			}
			// 当前到最近叶
			dis2Leaf.put(root.val, disLeaf + 1);
		}

		int dis2t = -1;
		if (root.left != null && dist2Tar.containsKey(root.left.val)) {// targ在左子
			dis2t = dist2Tar.get(root.left.val) + 1;
		} else if (root.right != null && dist2Tar.containsKey(root.right.val)) {
			dis2t = dist2Tar.get(root.right.val) + 1;
		}
		if (dis2t != -1) {
			dist2Tar.put(root.val, dis2t);
		} else if (root.val == k) {
			dist2Tar.put(root.val, 0);
		}

		// 计算以当前节点为角度，看左右子
		int dis = Integer.MAX_VALUE;
		if (dist2Tar.containsKey(root.val)) {
			dis = dis2Leaf.get(root.val) + dist2Tar.get(root.val);
		}
		return Math.min(Math.min(le, ri), dis);
	}

	public int findClosestLeaf2(TreeNode root, int k) {
		helper(root, k);
		return res;
	}

	private int[] helper(TreeNode root, int k) {
		int[] ret = new int[3];// 0到叶节点的距离，1到目标的距离，2要返回的叶节点的值
		ret[0] = ret[1] = ret[2] = -1;
		int[] left = null, right = null;
		if (root.left == null && root.right == null) {
			ret[0] = 0;
			ret[2] = root.val;
		} else {
			if (root.left != null) {
				left = helper(root.left, k);
				ret[0] = left[0];
				ret[2] = left[2];
				if (left[1] != -1) {
					ret[1] = left[1] + 1;
				}
			}
			if (root.right != null) {
				right = helper(root.right, k);
				if (root.left == null || ret[0] > right[0]) {
					ret[0] = right[0];
					ret[2] = right[2];
				}
				if (right[1] != -1) {
					ret[1] = right[1] + 1;
				}
			}
			ret[0]++;
		}
		if (root.val == k) {// 如果就是当前值，设置找到
			ret[1] = 0;
			minDis = ret[0];
			res = ret[2];
		} else if (ret[1] != -1) {
			int dis = ret[0] + ret[1];
			if (dis < minDis) {
				minDis = dis;
				// 返回的节点数值是左右子传过来的其中一个叶的值，取叶距离小者
				if (root.left == null || left[0] > right[0]) {
					res = right[2];
				} else if (root.left != null) {
					res = left[2];
				}
			}
		}
		return ret;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		TreeNode t1 = new TreeNode(1);
		TreeNode t2 = new TreeNode(2);
		TreeNode t3 = new TreeNode(3);
		t1.left = t2;
		t1.right = t3;
		TreeNode t4 = new TreeNode(4);
		TreeNode t5 = new TreeNode(5);
		TreeNode t6 = new TreeNode(6);
		t2.left = t4;
		t4.left = t5;
		t5.left = t6;
		ClosestLeafinaBinaryTree closestLeafinaBinaryTree = new ClosestLeafinaBinaryTree();
		System.out.println(closestLeafinaBinaryTree.findClosestLeaf(t1, 4));
		System.out.println(closestLeafinaBinaryTree.dis2Leaf);
		System.out.println(closestLeafinaBinaryTree.dist2Tar);
	}

}
